package com.lw.leetcode.bingChaJi.c;

import com.lw.test.util.Utils;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1998. 数组的最大公因数排序
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/7 16:52
 */
public class GcdSort {

    public static void main(String[] args) {
        GcdSort test = new GcdSort();


        // true
//        int[] nums = {10, 5, 9, 3, 15};

        // true
//        int[] nums = {7, 21, 3};

        // false
//        int[] nums = {5, 2, 6, 2};

        //
        int[] nums = Utils.getArr(30000, 2, 1000);

        boolean b = test.gcdSort(nums);
        System.out.println(b);
    }

    public boolean gcdSort(int[] nums) {
        int length = nums.length;
        int[] arr = new int[length];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            int end = (int) Math.pow(num, 0.5);
            int j = 2;
            int item = -1;
            while (j <= end) {
                if (num % j == 0) {
                    num /= j;
                    int p = find(j, map);
                    if (item == -1) {
                        arr[i] = p;
                        item = p;
                        map.put(j, item);
                    } else {
                        map.put(p, item);
                    }
                    j = 2;
                } else {
                    j++;
                }
            }
            if (item == -1) {
                arr[i] = find(num, map);
            } else {
                if (num > 1) {
                    map.put(find(num, map), item);
                }
            }
        }
        Map<Integer, List<Integer>> ms = new HashMap<>();
        for (int i = 0; i < length; i++) {
            int c = find(arr[i], map);
            arr[i] = c;
            ms.computeIfAbsent(c, v -> new ArrayList<>()).add(nums[i]);
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (Map.Entry<Integer, List<Integer>> entry : ms.entrySet()) {
            Collections.sort(entry.getValue());
            counts.put(entry.getKey(), 0);
        }
        int[] values = new int[length];
        for (int i = 0; i < length; i++) {
            int index = arr[i];
            int c = counts.get(index);
            values[i] = ms.get(index).get(c);
            counts.put(index, c + 1);
        }
//        System.out.println(ms);
        Arrays.sort(nums);
        for (int i = 0; i < length; i++) {
            if (values[i] != nums[i]) {
                return false;
            }
        }
        return true;
    }

    private int find(int t, Map<Integer, Integer> map) {
        Integer v = map.get(t);
        if (v == null) {
            map.put(t, t);
            return t;
        }
        if (v == t) {
            return t;
        }
        int i = find(v, map);
        map.put(t, i);
        return i;
    }

}
